/**
 * 面试题 10.09. 排序矩阵查找（与 240 同）
 * https://leetcode-cn.com/problems/sorted-matrix-search-lcci/
 */
public class Solutions_mianshi_10_09 {
    public static void main(String[] args) {
//        int[][] matrix = {{1, 4, 7, 11, 15},
//                          {2, 5, 8, 12, 19},
//                          {3, 6, 9, 16, 22},
//                          {10, 13, 14, 17, 24},
//                          {18, 21, 23, 26, 30}};

//        int target = 5;  // output: true
//        int target = 20;  // output: false

        int[][] matrix = {{-5}};
        int target = -5;  // output: true

        boolean result = searchMatrix(matrix, target);
        System.out.println(result);
    }

    /**
     * 根据每一行、每一列都按升序排列的原则，
     * 对于每一个元素，左边的元素都是小于该元素的，下边的元素都是大于该元素的
     */
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length < 1) {
            return false;
        }
        // 从矩阵的右上角出发
        int row = 0, col = matrix[0].length - 1;
        while (row < matrix.length && col >= 0) {
            if (target == matrix[row][col]) {
                return true;
            } else if (target < matrix[row][col]) {
                // 小于矩阵值，在左边
                col --;
            } else {
                // 大于矩阵值，在下边
                row ++;
            }
        }
        // 说明矩阵中不存在 target
        return false;
    }
}
